package summer.hot100.v1;

public class Solution148 {
    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode B = slow.next;
        slow.next = null;
        ListNode A = head;
        A = sortList(A);
        B = sortList(B);
        return merge(A, B);
    }

    public ListNode merge(ListNode A, ListNode B) {
        if (A == null) return B;
        if (B == null) return A;
        if (A.val < B.val) {
            A.next = merge(A.next, B);
            return A;
        } else {
            B.next = merge(A, B.next);
            return B;
        }
    }
}
